package com.mc.search;

public class BinarySearchST<Key extends Comparable<Key>,Value> {
	private Key[] keys;
	private Value[] vals;
	private int N;
	public BinarySearchST(int capacity){
		keys = (Key[])new Comparable[capacity];
		vals = (Value[])new Object[capacity];
	}
	public Value get(Key key){
		if(isEmpty())return null;
		int i = rank(key);
		if(key.equals(keys[i])&&i<N)
			return vals[i];
		return null;
	}
	//rank  返回该键值在数组中的位置，即小于它的键值的个数
	public int rank(Key key){
		int low = 0;
		int high = N-1;
		while(low<=high){
			int mid = low+(high-low)/2;
			int compare = key.compareTo(keys[mid]);
			if(compare>0)
				low = mid+1;
			else if (compare<0)
				high = mid-1;
			else
				return mid;
		}
		return low;
	}
	public void put(Key key,Value val){
		int i = rank(key);
		if(i<N&&key.compareTo(keys[i])==0){
			vals[i] = val;
			return;
		}
		for(int j=N;j>=i;j--){
			keys[j]=keys[j-1];
			vals[j]=vals[j-1];
		}
		keys[i]=key;
		vals[i]=val;
		N++;
	}
	public boolean isEmpty(){
		if(N==0)
			return true;
		else
			return false;
	}
}
